Round Overview
Discuss this match
It is the 604-th edition of TopCoder’s Single Round Matches. This time the problem set was authored by cgy4ever. This match was full of challenging problems. Division 1 easy needed some nice ad hoc maths, it is always impressive to watch coders like Eryx solve these messy problems in less than 2 minutes. The medium problem was a dynamic programming one that required good observations and analysis if you don’t want it to get overcomplicated. Petr was significantly faster than everyone else in this problem precisely because he found the exact observation that simplifies everything quite quickly. The 1000 points problem was a beast of its own, requiring unusual Computational Geometry/Collision detection theory. This problem was Egor’s success, winning just a bit more points in this problem than Petr. Also notable, we could catch Gassa submitting the first successful python solution for a division 1 hard problem. The consistently good performance in all three problems scored Petr yet another division win. Second place went to Zlobober, also with nice consistency. Third place, still with over 1000 points was Egor’s to get. Division 2 was won by former gray coder HwhiteTooth, congratulations and welcome to division 1.
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 1208 / 1435 (84.18%) |
Success Rate | 975 / 1208 (80.71%) |
High Score | ye7ia for 248.16 points (2 mins 27 secs) |
Average Score | 185.91 (for 975 correct submissions) |
There are at most 50 words, which means at most 50*49/2 unordered pairs. (We should use unordered pairs because `(a,b)` is said to be the same as `(b,a)` by the problem statement. So we can actually just try all pairs of strings. If the pair is interesting, count it. The important challenge of the problem is to find if two strings make a interesting pair.
The condition for two strings `(S,T)` to make a interesting pair is that there are two strings `B` and `A` such that `S=A+B` and `T=B+A`.
Since `S = A + B` . `A` must be a prefix of `S` we can try just all prefixes of `S` as potential `A` prefixes. There are `O(n)` possible prefixes. Once you fix `A` to a particularly prefix of `S`, you can find `B` as the remaining parts of `S`. Concatenate `B+A` and if the result is equal to `T`, for any of the possible `A` candidates, the result is interesting:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool interesting(string s, string t) {
for (int i = 0; i < s.size(); i++) {
string a = s.substr(0, i); //first i characters of s
string b = s.substr(i); //characters of s after the first i ones
if (b + a == t) {
return true;
}
}
return false;
}
int howManyPairs(vector < string > words) {
int c = 0;
for (string a: words) {
for (string b: words) {
if (a < b) {
if (interesting(a, b)) {
c++;
}
}
}
}
return c;
}
Or in python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
class FoxAndWord: def howManyPairs(self, words): # Does any index i make a valid prefix and suffix ? def interesting(s, t) : return any(s[i: ] + s[0: i] == t for i in range(len(s))) # iterate through pairs of words def unorderedPairs(words): for s in words: for t in words: if s < t: yield(s, t) # we could do it in one line but this might be easier to read # main: return sum(interesting(s, t) for (s, t) in unorderedPairs(words))
PowerOfThreeEasy
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 975 / 1435 (67.94%) |
Success Rate | 560 / 975 (57.44%) |
High Score | agamagarwal for 498.99 points (1 mins 17 secs) |
Average Score | 337.77 (for 560 correct submissions) |
There were various solutions to this problem, let’s mention some of them.
A simplification that helps all of them is to stop thinking about two points and consider only one point. Usually, we are located in a point `(x_c,y_c)` and want to move to the input point `(x,y)`. Each move changes the current point’s coordinates. However, we can simplify this so that we can represent the state as just one vector: `(x,y)` featuring the relative difference between the objective and the current point. So if you move 1 unit up, the difference becomes `(x,y-1)` (The `y` difference decreases by 1). If you move to the right by `d_x` units, the `x` coordinate changes to `x-d_x`. The objective is reached when `(x,y)` becomes `(0,0)` in other words:
If it is possible to make `(x,y) = (0,0)`, return “Possible”.
If in step `k`, you move up, the position becomes `(x,y) = (x, y - 3^k)`.
If you move right, the position becomes `(x,y) = (x - 3^k, y)`.
The constraints for `x` and `y` tell us that they are at most `10^9`. A nice question is what is the maximum number of moves we can ever need?
Consider `x = 3^0 + 3^1 + 3^2 + … + 3^(t-1)`. This is the maximum value of `x` after `t` moves. If `t` is so large that `x` exceeds `10^9`, then we can claim that it is impossible to do `t` moves. If you simulate this you can find that if `t = 20`, `x` will exceed `10^9`, so the maximum number of moves we could need is 19.
The 19 moves limit is useful because each move is a choice and the number of options for each choice is 2. For each move, you choose up or right. This means that there are at most `2^19 = 524288` ways to select a move sequence. We can then just try all possible ways to select the move sequence. We can for example, use recursive backtracking. Start with `(x,y)` and the number of move `k = 0`. In each move, you choose up or right, modify `x` or `y` by subtracting `3^k` and proceed to the next step. If `x` or `y` ever becomes negative, we can stop, no later move can increase `x` or `y`, so it would be impossible to reach 0. If both `x` and `y` are 0, then we found a valid sequence of moves.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Initially 3^k = 1, if we increment k, it is the same as multiplying by 3
// helps us doing the backtracking easily.
string ableToGet(int x, int y, int p = 1) {
// if x or y was negative, it is impossible.
// Else if x==0 , y==0 it is already possible.
// else we backtrack, first subtracting p from x or y and remember to
// multiply p by 3.
if (
(x >= 0) && (y >= 0) &&
(
(x == 0 && y == 0) ||
(ableToGet(x - p, y, p * 3) == "Possible") ||
(ableToGet(x, y - p, p * 3) == "Possible")
)
) {
return "Possible";
} else {
return "Impossible";
}
}
A more clever algorithm starts as brute-force. If `(x,y) != (0,0)` then we need at least one step. The first step will be to decrease `x` or `y` by 1. After decreasing this unit, the values of `x` and `y` should both be equal to sums like: `3^(e_0) + 3^(e_1) + … 3^(e_r)`, where each `e_i` is at least 1. Assume `e_0` is the smallest exponent:
`x = 3^(e_0) + 3^(e_1) + … 3^(e_r)`
`x = 3(e_0)(30 + 3(e_1-e0) + … 3(e_r-e0))`
Since `e_0` is at least 1, then `3^(e_0)` is some power of 3 different to 1. Which means that `x` is a multiple of 3. Similarly `y` is a multiple of 3`. This might appear inconsequential, but there are two important facts that follow from it.
First remember the original `(x,y)` , we needed to decrease one of them. This means that `(x-1,y)` or `(x,y-1)` must be valid (both coordinates must be a multiple of 3). Notice that if `x-1` is a multiple of 3, `x` cannot be a multiple of 3. The same happens with `y`: `y` and `y-1` cannot both be a multiple of 3. Thus there is at most one valid choice for the first step given a `(x,y)`, we need to pick the one that makes both `x` and `y` a multiple of 3.
The second is that once we decrease one of them, and both `x` and `y` become multiples of 3, we can divide both by 3. Something interesting happens with them. Assume they are valid values, it means that `x` and `y` are sums of powers of 3, and the two numbers don’t share any exponents. Each exponent from 1 to `t` appears in the two sums. If we divide the two numbers by 3, it is the same as decreasing the exponent in each of the powers in the two sums, for example:
`x = 3^1 + 3^2 + 3^4 + 3^8`
`y = 3^3 + 3^5 + 3^6 + 3^7`
--------------------------------------
`x/3 = 3^0 + 3^1 + 3^3 + 3^7`
`y/3 = 3^2 + 3^4 + 3^5 + 3^6`
Now consider that `(x’,y’) = (x/3, y/3)` is the same as the original problem. Once again the allowed moves are powers of 3 and the initial step is `3^0`. So we can repeat it all. Once again we might need to decrease `x` or `y` by 1, then maybe divide by 3 and so and so. We should stop whenever we reach a `(x,y)` that cannot be converted into multiples of 3 after decrementing exactly one of them.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string ableToGet(int x, int y) {
// If (x==0, y==0, then it is possible).
while (x != 0 || y != 0) {
// decreasing one of x or y must yield a multiple of 3.
// so either x%3 == 1 and y%3 == 0 or
// x%3 == 0 and y%3 == 1.
// It can be reduced to the following condition:
if (x % 3 + y % 3 != 1) {
return "Impossible";
}
// Decrease one of them, divide them by 3.
// * If x % 3 == 1, then x/3 = (x-1)/3
// * Same with y.
x /= 3;
y /= 3;
}
return "Possible";
}
Or in python, without comments to showcase how small the code is:
1 2 3 4 5 6 7
class PowerOfThreeEasy: def ableToGet(self, x, y): while (x, y) != (0, 0): if x % 3 + y % 3 != 1: return "Impossible" (x, y) = (x / 3, y / 3) return "Possible"
Another method is to consider `x` and `y` as polynomials:
`x = x_0 (3^0) + x_1 (3^1) + … + x_t (3^t)`
`y = y_0 (3^0) + y_1 (3^1) + … + y_t (3^t)`
Where: each `x_i` and `y_i` is either 0 or 1. And `x_i != y_i` for each `i`.
So we consider both numbers as being sums of all powers of 3, but multiplied by some factors. `x_i = 0` means that `3^i` is not actually in the sum of `x`.
The cool thing about this is that polynomials like these are really base 3 numbers. So we can write `x` as base 3:
`x = (x_t)…(x_1)(x_0)`
Where `x_i` behave as digits.
It is easy to get the base-3 representations of `x` and `y`, then you just need to compare each digits, making sure that at least one of them is 1.
Something nice about this is that the code will actually be equivalent to the quick loop approach above. Consider doing `x%3` the same as extracting the digit in base 3. `x%3 + y%3==1` is true only when exactly one of the digits is 3. Dividing `x` and `y` by 3 is the same as removing the last digit.
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 28 / 1435 (1.95%) |
Success Rate | 7 / 28 (25.00%) |
High Score | Hwhitetooth for 729.61 points (18 mins 49 secs) |
Average Score | 572.37 (for 7 correct submissions) |
Count the number of ways to pick `k` cities such that they are connected. The cities make a tree. It follows that you need to count the number of sub-trees of `k` nodes from a larger tree. This problem is a classical one that possibly already has explanations out there, but let’s solve it with a dynamic programming that will also help explain the division 1 version.
If you are new to dynamic programming, try dumitru’s tutorial: Dynamic programming: from novice to advanced from the educational section.
We would like to find a sub-optimal structure in this problem. That is, a way to divide the problem into smaller subproblems. In problems where the graph is a tree, it is usually a good idea to start by rooting them, any arbitrary root is going to be fine, let’s go with node 0 as a root.
The sub-tree of `k` nodes that we pick should have a root of its own. How about we use that as a starting point? There are `O(n)` options for the root of the sub-tree. For each of them, count the number of ways to make a sub-tree that is rooted there.
We want to count the number of sub-trees of `k` nodes rooted at node `x`. Let’s call the function that solves this `f(x,k)`.
It is a good thing trees are a recursive data structure. The node `x` will have some children and each of those children can be seen as a subtree. Of the `k` nodes that should be part of the sub-tree, one will be `x`, the remaining `k-1` nodes have to be distributed between these children.
Consider a node `x` with 3 children: `a`, `b` and `c`. Assume we picked `k_a`, `k_b` and `k_c` as the number of nodes from `a`, `b` and `c` that will be used in the picked sub.tree. `k_a + k_b + k_c + 1 = k`. Any subtree rooted at `a` that has `k_a` elements will be a valid part of the result, same with `b` and `k_b` and `c` and `k_c`. We can find the number of ways to pick the nodes in each subtree as `f(a, k_a)`, `f(b, k_b)` and `f(c, k_c)`, respectively. These choices are independent (the nodes we pick from subtree `a` won’t alter the available options in `b`) so we can find the total number of ways to pick subtrees given `k_a`, `k_b` and `k_c` as: `f(a, k_a) * f(b, k_b) * f(c, k_c)`.
While this shows that we can divide the problem in smaller sub-problems, we have a new issue: How to iterate through all the ways to choose the number of elements that will go to each child subtree? We could nest a dynamic programming there, but an arguably simpler approach is to divide the sub-problems in a different way.
The trick here is not to distribute `k-1` between all the children, but only between the left-most child and the rest. Like this:
This time we solve a function `f(x, e, k)` that returns the number of ways to have a subtree of `k` nodes using `x` as root and without using the first `e` children of x.
If `e` is equal to the number of children of `x`, it means that we can only use the root, `x` . If `k` is equal to 1, there is exactly one way to make a subtree that has only one element (take `x` as the sole element of the subtree).
Else we have at least one child. The left-most child will have index `e` in the list of children of `x`. Now we know that one of the `k` nodes will be the root, `x`. We can distribute some of the nodes in the sub-tree rooted at child `e`. We can try all the possibilities for the number of nodes that will belong to the subtree `i`. Let’s say `y` is child #e of `x`: There are `f(y, 0, i)` ways to distribute `i` nodes with this subtree (Because we can use all its children, so `e=0`). There are `f(x, e+1, k - i)` ways to distribute the remaining nodes with the rest of the subtree rooted at `x`. For each `i` we can find the result as: `f(y,0,i)*f(x, e+1, k - i)`
There are some details to consider. `k - i` shouldn’t be 0, because we need the root `x` to be one of the picked nodes. Also, we are able to choose not to put any node in the child `y`. This means that the provided `k` to `f(x,e,k)` can be 0. In this case, there is exactly one way to pick zero nodes, so the result is 1.
A complexity analysis: There are `O(n)` `(x,e)` pairs, because there are at most `2n-1` such pairs in total. Consider that each `(x,e)` represents either a child node or the root when `e` is equal to the degree, so most nodes will appear in two `(x,e)` pairs, except for the tree’s root, which will appear only once. So there are `O(nk)` `(x,e,k)` tuples. Each call to `f(x,e,k)` might need an `O(k)` loop to pick `i`. We are using dynamic programming so that each `(x,e,k)` tuple is evaluated at most once. So the algorithmic complexity is `O(nk^2)`. This is even when we consider the `O(n)` loop to pick the root of the subtree, regardless of how it calls `f()`, `f()` will be evaluated at most `O(nk)` times.
Problems that ask you to return the result modulo 1,000,000,007 (or a similar number) usually do so to allow us to solve problems that have large results without actually using those large numbers in calculations. We can handle these numbers with modular arithmetic. Read this recipe for more info.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
static
const int MOD = 1000000007;
static
const int MAX = 50;
int n;
int degree[MAX];
int g[MAX][MAX];
string haveFox;
void dfsMakeTree(int x, int parent, vector < int > & A, vector < int > & B) {
degree[x] = 0;
for (int i = 0; i < n - 1; i++) {
if ((A[i] - 1 == x) && (parent != B[i] - 1)) {
g[x][degree[x]++] = B[i] - 1;
dfsMakeTree(B[i] - 1, x, A, B);
}
if ((B[i] - 1 == x) && (parent != A[i] - 1)) {
g[x][degree[x]++] = A[i] - 1;
dfsMakeTree(A[i] - 1, x, A, B);
}
}
}
int mem[MAX][MAX + 1][MAX];
long rootedWays(int x, int k, int e) {
// number of ways to have a tree of k nodes that is rooted at node x.
// if we already processed e of its edges.
long res = mem[x][k][e];
if (res == -1) {
res = 0;
if (k == 0) {
res = 1;
} else if (e == degree[x]) {
//processed all edges.
res = ((k == 1) ? 1 : 0);
} else {
//how many must go to child #e?
for (int i = 0; i < k; i++) {
long p = rootedWays(g[x][e], i, 0);
long q = rootedWays(x, k - i, e + 1);
res += (p * q) % MOD;
}
}
res %= MOD;
mem[x][k][e] = (int) res;
}
return res;
}
int ways(vector < int > A, vector < int > B, int k) {
this - > n = A.size() + 1;
fill(degree, degree + n, 0);
dfsMakeTree(0, -1, A, B);
memset(mem, -1, sizeof(mem));
long sum = 0;
for (int i = 0; i < n; i++) {
sum += rootedWays(i, k, 0);
//cout << sum << " " << i << endl;
}
return (int)(sum % MOD);
}
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 649 / 845 (76.80%) |
Success Rate | 494 / 649 (76.12%) |
High Score | Eryx for 248.69 points (2 mins 3 secs) |
Average Score | 166.66 (for 494 correct submissions) |
A good approach is to use the same logic we used for the “quick loop” approach in the division 2 version: PowerOfThreeEasy.
In the first step, we have 4 options: Increment `x`, decrease `x`, increment `y` and decrease `y`.
After that operation `x` and `y` must both be multiples of 3.
Notice that exactly one of `x-1`, `x` and `x+1` can be a multiple of 3. E.g: If `x` is a multiple of 3, then `x -= 0 mod 3` which means `x-1 -= 2 mod 3` and `x+1 -= 1 mod 3`. So we take `x mod 3`, if the result is 0, we cannot increment nor decrement `x`. If the result is 1, we should decrement `x` and if the result is 2, we should increment `x`. Same with `y`
When no valid move is possible, we can return “Impossible”.
If a valid move is possible, both `x` and `y` become multiples of 3 and we can divide both by 3 and return to the initial problem, just like in the division 2 version.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
string ableToGet(int x, int y) {
// to save us the issue of dealing with the % operation being flawed with
// negative numbers, we can just use some symmetry,
// (x,y) is reachable if and only if (-x,y), (-x,-y) and (x,-y) are.
x = abs(x);
y = abs(y);
while (x != 0 || y != 0) {
// one of x,y must be a multiple of 3, the other shouldn't.
if ((x % 3 == 0) && (y % 3 != 0)) {
// If y % 3 == 2, the result is y/3 + 1 or (y+1) / 3.
if (y % 3 == 2) {
y = (y + 1) / 3;
} else {
y = (y - 1) / 3;
}
x /= 3;
} else if ((y % 3 == 0) && (x % 3 != 0)) {
if (x % 3 == 2) {
x = (x + 1) / 3;
} else {
x = (x - 1) / 3;
}
y /= 3;
} else {
return "Impossible";
}
}
return "Possible";
}
As an interesting exercise, find why the following code is equivalent:
1
2
3
4
5
6
7
8
9
10
11
12
13
string ableToGet(int x, int y) {
x = abs(x);
y = abs(y);
while (x != 0 || y != 0) {
if ((x % 3 == 0) != (y % 3 == 0)) {
y = (y + (y % 3 == 2)) / 3;
x = (x + (x % 3 == 2)) / 3;
} else {
return "Impossible";
}
}
return "Possible";
}
Or in python:
1 2 3 4 5 6 7 8 9
class PowerOfThree: def ableToGet(self, x, y): while x != 0 or y != 0: if (x % 3 == 0) != (y % 3 == 0): y = (y + (y % 3 == 2)) / 3 x = (x + (x % 3 == 2)) / 3 else: return "Impossible" return "Possible"
There are more simplifications explained in the shortest code thread. A thread in which coders try to minimize the size of the solution.
Used as: Division One - Level Two:
Value | 550 |
Submission Rate | 180 / 845 (21.30%) |
Success Rate | 20 / 180 (11.11%) |
High Score | Petr for 453.20 points (13 mins 45 secs) |
Average Score | 258.04 (for 20 correct submissions) |
The main idea is that, since the cities make a tree, we can try a dynamic programming idea similar to the one used in the division 2 version. I think that some knowledge about how to solve those problems is useful here, so make sure to read that explanation before reading this one.
You will find that trying to come up with a dynamic programming that runs in time will be problematic and it will be complicated to implement, unless we make a very good observation.
The main issue is to keep track of how the foxes are moving around the graph. If we take an arbitrary root as the root of the final subtree of foxes. That means that all the foxes in other subtrees above it must move to the tree. This contains a cost. However, there is also how foxes in bottom subtree have to move up at times. This is all complicated until we notice an invaluable property:
There are `t` foxes in total. Imagine we decided that we want `k` foxes to go to the subtree rooted at node `x`. Notice that it is easy to know the total number of foxes that are initially in this sub-tree (We just need a small DFS to count this for each node as a root). Let `m` be the number of foxes in the subtree: Then we have three cases:
`k - m = 0`. This means that we should use the exact same foxes that are already in the sub-tree.
`k - m > 0`. This means there are `(k - m)` foxes that must come from outside this subtree.
`k - m < 0`. This means there are `(m - k)` foxes that must move from the subtree to outside it.
Since `m` is constant, each value of `k` will determines the value of `(k-m)`. This means that we only need tuple `(x, e, k)` to represent the state. (Where `(x,e)` represent a root `x` and the number of edges already-processed like in the division 2 version). The rest is to figure the logic out. Let’s think of a function `f(x, e, k)` that returns the minimum cost to make a sub-tree of `k` nodes rooted at `x` when we are not allowed to use the first `e` children of `x`.
We must assume that whenever `f(x,0, k)` is called, with a given `k`. If there are `m` foxes in the sub-tree rooted at `x`, then we need to make assumptions:
If `(k - m > 0)` there are some foxes outside the subtree that should move towards it. We can assume that the `(k - m)` necessary foxes will eventually reach `x`. So later when we move them down we can assume that they will exist. If `f(x,0,k)` is called we need to be sure that those foxes move there. First of all, when picking the root of the total subtree, make sure to calculate the cost to move all of the outside foxes. The other situation is when calling `f(y,0,k=i)` for a child of `x`, we should make sure to also calculate the cost to move the necessary foxes from `x` to `y`. If there are `m_y` foxes in the subtlee of `y`, this cost is equal to `i - m_y`
If `(m - k > 0)`, then there are foxes that will not be used in the subtree. These foxes must move out of the tree. We should assume that when calling `f(x,0,k)` , it will mean that `m - k` foxes will move up to `x`. When we call `f(y,0, i)` as part of the solution for `f(x, 0, k=i)` and there are `(m_y - i > 0)` foxes that must leave the sub-tree rooted at `y`, it means that we should move these `(m_y - i)` foxes from `y` to `x`. The cost is equal to `m_y - i`.
Now notice that in both cases, we need to consider a cost of `|i - m_y|`, the absolute value. We either move foxes from `y` to `x` or from `x` to `y`.
The recurrence relation `f(x,e,k)` has taken shape:
If `e` is equal to the number of children of `x`, it means that we only need to find the minimum cost to distribute `k` foxes in the node `x`. `k` must be at most 1 for this to be valid. The minimum cost is 0 in that case. We assume that if there was no fox in `x`, we already moved it there in some previous step.
Else we say that `y` is child number #e of `x`. We should distribute up to `k-1` foxes to `y`. Let `i` be the number of foxes that will be assigned to subtree `y`. Then we will eventually need `|m_y - i|` cost to move foxes from `x` to `y` or vice versa. The additional cost is: `f(y,0,i) + f(x, e+1, k-i)`
In order to calculate this, we should first know the minimum cost to move all the foxes in a subtree to its root `x`. This cost is actually equal to `f(x,0, k=0)`. The cost to pick zero nodes in this subtree.
This reminds us that `k` can be 0 in the recurrence. If `k=0`, then the number of foxes to distribute to children will always be 0 as well. We just need to count the cost to move any fox in the depths of this subtree towards node `x`.
Finally, we need to pick the subtree root and calculate its cost. We can use another recursive logic. Solution `g(x)` finds the minimum cost to pick a root inside subtree rooted at `x`.
We can pick `x` as the root. Then the cost is simply `f(x,0, t)`.
Else the root would belong to one of the children. Calculate the cost to pick branch `y`. There are `t` total foxes. So if `m_x` is the number of foxes in the subtree rooted at `x`, it means that `t - m_x` foxes moved to `x`. These foxes and also the fox located at `x` (if it exists) are added to the cost. We also should move any fox from the other children to `x` and then to `y`. For each child `z != y`: `f(z,0,k=0)` is the cost to move all its foxes to `z`, then you need `2m_z` moves to move the foxes from `z` to `x` and then to `y` . All these costs are added to `g(y)`.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
static
const int MAX = 50;
int n;
vector < int > g[MAX];
string haveFox;
void dfsMakeTree(int x, int parent, vector < int > & A, vector < int > & B) {
// make the contents of g[i] for all is.
for (int i = 0; i < n - 1; i++) {
if ((A[i] - 1 == x) && (parent != B[i] - 1)) {
g[x].push_back(B[i] - 1);
dfsMakeTree(B[i] - 1, x, A, B);
}
if ((B[i] - 1 == x) && (parent != A[i] - 1)) {
g[x].push_back(A[i] - 1);
dfsMakeTree(A[i] - 1, x, A, B);
}
}
}
int subtreeFoxes[MAX]; //[i]: total number of foxes in subtree rooted at i
// finds the number of foxes in each subtree.
void dfsCountFoxes(int x) {
subtreeFoxes[x] = (haveFox[x] == 'Y');
for (int y: g[x]) {
dfsCountFoxes(y);
subtreeFoxes[x] += subtreeFoxes[y];
}
}
const int INF = 50000;
int totalFoxes;
int cost[MAX][MAX][MAX + 1];
int theCost(int x, int e, int k) /* O(n*k) states */ {
int & res = cost[x][e][k];
if (res == -1) {
if (e == g[x].size()) {
// base case, e is equal to the number of children
res = ((k <= 1) ? 0 : INF);
} else {
// We can search for the best i for the number of foxes in y.
res = INF;
int y = g[x][e];
int maxi = ((k == 0) ? 0 : (k - 1));
for (int i = 0; i <= maxi; i++) {
// cost of the decision:
int p = abs(i - subtreeFoxes[y]) + theCost(y, 0, i);
// absolute value because we might need to move foxes from
// x to y or vice versa depending on the case.
int q = theCost(x, e + 1, k - i);
res = std::min(res, p + q);
}
}
}
return res;
}
int best[MAX];
void dfsBestSubtree(int x) {
// try picking x as the root of the subtree:
best[x] = theCost(x, 0, totalFoxes);
// total foxes currently in x:
int inNode = totalFoxes - subtreeFoxes[x] + (haveFox[x] == 'Y');
for (int y: g[x]) {
// Solve the costs for y and its children
dfsBestSubtree(y);
// Additional cost:
int sumCost = inNode;
for (int z: g[x]) {
if (z != y) {
// move from z to x and then to y
sumCost += theCost(z, 0, 0) + 2 * subtreeFoxes[z];
}
}
best[x] = std::min(best[x], sumCost + best[y]);
}
}
int minimalDistance(vector < int > A, vector < int > B, string haveFox) {
totalFoxes = count(haveFox.begin(), haveFox.end(), 'Y');
if (totalFoxes == 0) {
return 0;
}
this - > haveFox = haveFox;
n = haveFox.size();
// root the tree at 0:
dfsMakeTree(0, -1, A, B);
dfsCountFoxes(0);
memset(cost, -1, sizeof(cost));
dfsBestSubtree(0);
return best[0];
}
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 41 / 845 (4.85%) |
Success Rate | 9 / 41 (21.95%) |
High Score | Egor for 769.66 points (16 mins 37 secs) |
Average Score | 561.04 (for 9 correct submissions) |
After placing a number of crests in the plane, we don’t care much about their absolute positions but about the relative positions between them. Let’s formalize a rule to describe if two crests intersect when the relative offset is `(dx,dy)`. In other words, we add `dx` to the `x` coordinate and `dy` to the `y` coordinate of each segment end-point of the original crest to create a copy crest. What determines if `(dx,dy)` causes an overlap?
If `(dx,dy)` causes an overlap, it means that there exists a point `P` in the original crest that intersects with a point in the copy. This point in the copy is is generated by adding `(dx,dy)` to a point in the original crest. In short, there are at least two points `P` and `Q` in the crest such that `(Q_x + dx, Q_y + dy) = (P_x, P_y)`
We can now define how the set `S` of invalid offsets `(dx,dy)` looks like. From each of the possible pairs `(P, Q)` of points that belong to the crest, their difference `(dx,dy) = (P - Q)` makes an invalid offset. `P` and `Q` come from distinct segments of the crest. What we can do is this: For each pair of segments `bar(AB)` and `bar(CD)` in the crest, we pick all pairs `(P,Q)` of points `P in bar(AB)` and `Q in bar(CD)`. The union of all those `P - Q` is the result.
Each pair of segments `( bar(AB), bar(CD) )` will determine an area of points. `S` is actually the union of all the sets of points determined by each pair of segments.
Finally, we should imagine what happens when we draw `S` in a plane. Each valid `(dx,dy)` representing a point. It turns out that the `(dx,dy)` generated by a pair of segments `( bar(AB), bar(CD) )` will form a parallelogram. First of all, consider that points `A` and `B` are candidates for `P` and `C` and `D` are candidates for `Q`. So the points `{A-C, A-D, B-C, B-D}` are part of the set. We should show that those points are the corners of the parallelogram. Consider parameters `(0 <= s, t <= 1)` such that we can represent the points in `bar(AB)` as any point `P = sA + (1-s)B` and the points in `bar(CD)` as `Q = tC + (1-t)C`. Then for each `(s,t)`, the point `(P - Q = sA + (1-s)B - tC + (1-t)C)` will exist in `S`. From this it will follow that all the points `(s,t)` in a square with coordinates between 0 and 1, inclusive are projected into a parallelogram.
We have learned that the set `S` of invalid `(dx,dy)` pairs we can use for the offset can be calculated as the union of `O(n^2)` parallelograms. How can we use this knowledge to answer the initial question of the problem?
Imagine the `(0,0)` was inside `S`. This means that there is circle of non-zero radius `r` that contain points `(dx,dy)` that are invalid. This determines a minimum distance between crests. If the distance between two crests was less or equal to than `r`, an overlap forcibly happen as all points with distance smaller than `r would overlap with the original crest. Since there is a minimum distance between crests, it is not possible to fill the very large, but finite allocated escape using infinitely many crests.
If `(0,0)` was not inside `S`. Then we should be able to find a line segment starting at `(0,0)` and ending somewhere such that this line segment, does not visit any invalid point. Each of the points in this line segment is valid, and there are infinitely points inside a line segment. Which would mean it is quite possible to make an infinite number of crests.
A corner case: What if `(0,0)` is inside but not strictly inside? IF `(0,0)` lies exactly on the boundary of the set; We would still be able to draw the above-mentioned line segment that contains an infinite of replies.
In short, the problem is infinite if and only if `(0,0)` is strictly inside `S`.
We are given a list of parallelograms and we’t like to know if the union of those parallelogram strictly contains the origin.
If a single parallelogram from the input strictly contains `(0,0)`; We can just return that Yes, the union will strictly contain the origin.
Similarly, if `(0,0)` is already outside the parallelogram, we should just ignore `(0,0)`.
A final complication is what happens when `(0,0)` lies exactly on the boundary of a parallelogram; It is key to notice that this doesn’t necessarily mean that `(0,0)` exists only on the boundary of the total union. It is quite possible that, multiple boundaries cover `(0,0)` and cause it to stop being a boundary, for example:
The union of the parallelograms that have `(0,0)` in the boundary may still end up containing it strictly inside it. The solution in this case is to consider the angle between the boundary of each of those parallelograms and `(0,0)`. If the boundary angles fill a full circle, `(0,0)` is strictly inside, else it will lie on a boundary.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
struct point {
int x, y;
};
const double PI = acos(-1.0);
const double EPS = 1e-9;
// a list of angles
vector < pair < double, int > > v;
void add(double theta, int d) {
v.push_back(make_pair(theta, d));
}
void add_bad_angle(double L, double R) {
if (L < R) {
add(L, 1);
add(R, -1);
} else {
add(0, 1);
add(R, -1);
add(L, 1);
add(PI, -1);
}
}
// Check angles:
bool check(void) {
int i, d = 0;
sort(v.begin(), v.end());
for (int i = 0; i < v.size() - 1; i++) {
d += v[i].second;
if (d == 0 && v[i + 1].first > v[i].first + EPS) {
return true;
}
}
return false;
}
// Gets the angle between two points.
double angle(point P, point Q) {
double theta = atan2(Q.y - P.y, Q.x - P.x);
if (theta < 0.0) {
theta += PI;
}
return theta;
}
// Returns the sign of the triangle area. It determines if points are in clockwise
// order, colinear or anti-clockwise order.
int area(point P, point Q, point R) {
int s = (Q.x - P.x) * (R.y - P.y) - (Q.y - P.y) * (R.x - P.x);
if (s > 0) return 1;
if (s < 0) return -1;
return 0;
}
string canBeInfinite(vector < int > A, vector < int > B, vector < int > C, vector < int > D) {
int i, j;
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < i; j++) {
if ((C[i] - A[i]) * (D[j] - B[j]) == (D[i] - B[i]) * (C[j] - A[j])) {
// strictly outside, ignore this quad.
continue;
}
// Make the quad.
point V = {
A[i],
B[i]
}, U = {
C[i],
D[i]
}, R = {
A[j],
B[j]
}, S = {
C[j],
D[j]
};
int s1 = area(V, U, R) * area(V, U, S);
int s2 = area(R, S, V) * area(R, S, U);
if (s1 == 1 || s2 == 1) continue;
if (s1 != 0 || s2 != 0) {
// strictly inside.
return "Finite";
}
if (area(V, U, R) == 0) swap(V, S);
if (area(R, S, U) == 0) swap(V, U);
if (area(V, U, R) == -1) swap(U, R);
add_bad_angle(angle(V, R), angle(V, U));
}
}
add(0, 0);
add(PI, 0);
bool ans = check();
return (ans ? "Infinite" : "Finite");
}